package Lee_code;

import java.text.DateFormatSymbols;
import java.util.ArrayList;
import java.util.List;

/**
 * @author blh
 * @date 2024年07月31日 14:25
 */
public class Lee_210_731 {
    List<List<Integer>> edges;
    // 1是正在搜索, 2是已完成搜索, 0是未搜索
    int[] seen;
    int[] res;
    boolean valid = true;
    int index;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        index = numCourses;
        seen = new int[numCourses];
        res = new int[numCourses];
        edges = new ArrayList<>();
        // 初始化有向图
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }
        for (int[] prerequisite : prerequisites) {
            edges.get(prerequisite[1]).add(prerequisite[0]);
        }
        // 开始遍历
        for (int i = 0; i < numCourses; i++) {
            if (seen[i] == 0) {
                dfs(i);
            }
        }
        if (!valid) {
            return new int[0];
        }
        return res;
    }

    private void dfs(int i) {
        seen[i] = 1;
        for (Integer integer : edges.get(i)) {
            if (!valid) {
                return;
            }
            if (seen[integer] == 1) {
                valid = false;
                return;
            }
            if (seen[integer] == 0) {
                dfs(integer);
            }

        }
        seen[i] = 2;
        res[--index] = i;
    }
}
